package 其他.LinkedList;

import 其他.DataStructure.ListNode;
import org.junit.Test;

/**
 * 思路：
 *     cur cur.next tmp
 *     双节点移动
 *
 * 大领悟：
 *  草图 不用笔画，用注释画更清晰 !? 【太好用了！心里踏实了有神技了！！‍】
 *
 * 反转链表：
 *  无论 dg dd 都要 消 最开始的 a->b
 *
 *
 * a -> b -> c -> d -> e
 * 递归
 *   ->
 *   <-
 *
 * a -> b -> c -> d -> e
 * 迭代？
 * a    b    c
 *      a    b    c  移动ab b跟出c
 * 终止条件？[脑乱，画注释即清]
 *           a    b    c
 *                a    b    c
 *                     a    b   c ( w b!=null )
 *
 */
public class ReverseList {
    /* 递归 */
    public ListNode resNewHead = null;
    public ListNode reverseListUseDiGui(ListNode head) {
        if(head == null || head.next == null) return head;
        // 转
        reverseAndReturnNewHead(head, head.next);
        // 去掉 a->b
        head.next = null;
        // 返回 newHead
        return resNewHead;
    }
    public void reverseAndReturnNewHead(ListNode curNode, ListNode nextNode){
        if(nextNode == null){
            resNewHead =  curNode;
            return;
        }
        // 中文架先
        // ab 转前 留c (<-向左掰 会丢右侧箭头->， 所以tmp暂存)
        ListNode nextNodenext = nextNode.next;
        // b指a
        nextNode.next = curNode;
        // 下轮 cur=b ， next=c
        reverseAndReturnNewHead(nextNode, nextNodenext);
    }
    /* 迭代 */
    public ListNode reverseListUseDieDai(ListNode head) {
        if(head == null || head.next == null) return head;
        // 中文
        ListNode a = head;
        ListNode b = head.next;
        // ❌ 少删 a->b
        a.next = null;
        // ( w b!=null )
        while(b != null){
            // 准备：
            //  b跟出c
            ListNode c = b.next; // 后优化代码 把上方c去掉了
            // 转：
            //  ab反转
            b.next = a;
            // 下轮：
            //  a=b
            a = b;
            //  b=c
            b = c;
        }
        return a;
    }

    @Test
    public void test(){
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        // reverseListUseDiGui(l1); // digui - ac

        ListNode newH = reverseListUseDieDai(l1);
        System.out.println(1);
    }
}
